/***尚硅谷Java数据结构与java算法                    ***/
/***https://www.bilibili.com/video/BV1E4411H73v   ***/
/***使用栈实现一个计算器，可实现多位数的加减运算      ***/
/***利用栈  实现中缀表达式                          ***/
/***C++ 实现版本    written by Daniel              ***/
#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;
template <class T>
class Stack
{
public:
    Stack(int maxSize)
    {
        this->maxsize = maxSize;
        //开辟堆区数组
        arrayStack = new T[maxsize];
        return;
    }
    bool isEmpty()
    {
        return top == -1;
    }
    bool isFull()
    {
        return top == (maxsize - 1);
    }
    void push(T value)
    {
        if (isFull())
        {
            cout << "栈满，添加元素失败！" << endl;
            return;
        }
        arrayStack[++top] = value;
        return;
    }
    //看栈顶的值，但是并不出栈
    T peek()
    {
        if (this->isEmpty())
        {
            cout << "栈为空！" << endl;
            return -1;
        }
        return arrayStack[top];
    }

    T pop()
    {
        if (isEmpty())
        {
            cout << "栈空，无法取出元素！\n"
                 << endl;
            return -1;
        }
        return arrayStack[top--];
    }
    ~Stack()
    {
        if (arrayStack != nullptr)
        {
            delete[] arrayStack;
            arrayStack = nullptr;
        }
        cout << "析构成功" << endl;
    }
    void list()
    {
        int temp = top;
        if (this->isEmpty())
        {
            cout << "栈为空！" << endl;
            return;
        }
        for (int i = temp; i > -1; i--)
        {
            cout << "stack[" << i << "]"
                 << "=" << arrayStack[i] << endl;
        }
        return;
    }
    //补充三个方法，计算
    T calculate(T num1, T num2, int oper)
    {
        T res = 0;
        switch (oper)
        {
        case '+':
            res = num1 + num2;
            break;
            //注意减号的顺序
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num1 * num2;
            break;
            //注意减号的顺序
        case '/':
            res = num2 / num1;
            break;
        default:
            break;
        }
        return res;
    }
    //符号比较优先级
    int priority(int oper)
    {
        if (oper == '*' || oper == '/')
            return 1;
        else if (oper == '+' || oper == '/')
            return 0;
        else
            return -1;
    }

    bool isOperator(int oper)
    {
        if (oper == '+' || oper == '-' || oper == '*' || oper == '/')
            return true;
        else
            return false;
    }

private:
    int maxsize;
    T *arrayStack;
    int top = -1;
};

int main(int argc, char **argv)
{
    Stack<int> numStack(20);
    Stack<int> operStack(20);
    string expression = "40+2*6/3+50*8-3";
    cout<<"请输入需要计算的表达式"<<endl;
    std::cin>>expression;
    int num1 = 0, num2 = 0, res = 0;
    int index = 0;
    char oper = ' ';
    char preOper = ' ';
    while (true)
    {
        oper = expression[index];
        if (operStack.isOperator(oper))
        {
            //判断符号栈是否为空 或者  优先级大于栈顶符号栈
            if (operStack.isEmpty() || (operStack.priority(oper) > operStack.priority(operStack.peek())))
            {
                operStack.push(oper);
            }
            //当前符号优先级小于等于栈顶优先级，取出两个数和栈顶符号进行计算，结果进入数栈；再将符号压入符号栈
            else
            {
                num1 = numStack.pop();
                num2 = numStack.pop();
                res = numStack.calculate(num1, num2, operStack.pop());
                numStack.push(res);
                operStack.push(oper);
            }
        }
        else
        {
            //栈为空  或者  上个符号为 运算符
            if (numStack.isEmpty()||numStack.isOperator(preOper))
            {
                numStack.push(oper - '0');
            }//否则通过栈  取出真正的多位数
            else{
                res=numStack.pop()*10+(oper-'0');
                numStack.push(res);
            }
        }
        index++;
        preOper = oper;
        if (index >= (expression.size()))
        {
            break;
        }
    }
    numStack.list();
    operStack.list();
    while (!operStack.isEmpty())
    {
        num1 = numStack.pop();
        num2 = numStack.pop();
        res = numStack.calculate(num1, num2, operStack.pop());
        numStack.push(res);
    }
    cout << "result=" << numStack.peek() << endl;
    system("pause");
    return 0;
}